/************************************************************************
                                                                     
   Xceed Ultimate ListBox for Silverlight                                                                                                                                            
   Copyright (C) 2010 Xceed Software Inc.    
                                                                     
   This program is provided to you under the terms of the GNU General Public  
   License version 2 as published by the Free Software Foundation. 
        
   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY, without even the implied warranty of 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along 
   with this program, if not, write to the Free Software Foundation, Inc., 
   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

   This program can be provided to you by Xceed Software Inc. under a
   proprietary commercial license agreement for use in non-Open Source
   projects. Visit Xceed.com to find the commercial edition of 
   Xceed Ultimate ListBox for Silverlight.                                    
                                                                      
 **********************************************************************/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Windows.Threading;

namespace Xceed.Silverlight.Data
{
  internal class BufferingEnumerator<T> : CacheEnumerator<T>
  {
    #region Static Fields

    private static readonly Guid JumpMoveAndFetchCallId = DataUtils.CreateCallId();
    private static readonly Guid PassivePreFetchingCallId = DataUtils.CreateCallId();
    private static readonly Guid ActivePreFetchingCallId = DataUtils.CreateCallId();

    #endregion

    #region Constructor

    internal BufferingEnumerator(
      IAsyncEnumerator<T> childEnumerator,
      IDataHelper dataHelper,
      IBufferConfigurable bufferManager )
      : base( 0, dataHelper, childEnumerator )
    {
      m_bufferManager = bufferManager;
    }

    #endregion

    public override JumpMoveAndFetchAsyncResult BeginJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback callback,
      object state )
    {
      JumpMoveAndFetchAsyncResult asyncResult = new JumpMoveAndFetchAsyncResult(
                                                  BufferingEnumerator<T>.JumpMoveAndFetchCallId,
                                                  callback,
                                                  state,
                                                  parameters );

      // Try to retrieve the items from the buffer.
      bool isInBuffer = this.PeekBuffer( parameters, asyncResult );

      if( !isInBuffer )
      {
        // Some items aren't in the buffer.  We'll have to query the underlying enumerator
        // to retrieve the requested items.
        this.EnqueueQuery( parameters, asyncResult );
      }

      return asyncResult;
    }

    public override JumpMoveAndFetchResult<T> EndJumpMoveAndFetch(
      JumpMoveAndFetchAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( BufferingEnumerator<T>.JumpMoveAndFetchCallId );

      return asyncResult.GetCallResult<JumpMoveAndFetchResult<T>>();
    }

    protected override void ChildDataChanged( DataChangedEventArgs args )
    {
      if( args.Action == DataChangedAction.Reset )
      {
        this.StopPreFetching();
      }

      base.ChildDataChanged( args );
    }

    protected override void TrimCache(
      int removeCount,
      int topLimitIndex,
      out int removeFromStart,
      out int removeFromEnd )
    {
      if( ( removeCount == 0 )
        || ( m_centerOfGravity == null ) )
      {
        base.TrimCache(
          removeCount,
          topLimitIndex,
          out removeFromStart,
          out removeFromEnd );

        return;
      }

      int cacheSize = this.CachedItems.Count;
      int sourcePositionIndex = this.FindSourcePositionIndex( m_centerOfGravity, 0, 1 ).GetValueOrDefault( -1 );

      if( ( sourcePositionIndex < 0 )
        || ( sourcePositionIndex >= cacheSize )
        || ( cacheSize - removeCount <= 0 ) )
      {
        base.TrimCache(
          removeCount,
          topLimitIndex,
          out removeFromStart,
          out removeFromEnd );

        return;
      }
      else if( ( cacheSize - removeCount ) == 1 )
      {
        removeFromStart = sourcePositionIndex;
        removeFromEnd = removeCount - removeFromStart;

        return;
      }

      // Remove the right amount of items to get the selected item near the center 
      // of gravity.
      int expectedSourcePositionIndex = ( int )Math.Ceiling( m_bufferInfo.CenterOfGravity * ( cacheSize - removeCount ) );
      removeFromStart = Math.Min( sourcePositionIndex - expectedSourcePositionIndex, removeCount );
      removeFromEnd = Math.Min( removeCount - removeFromStart, removeCount );

      // Make sure we aren't removing none existing items.
      if( removeFromStart < 0 )
      {
        removeFromStart = 0;
      }
      else if( removeFromEnd < 0 )
      {
        removeFromStart += -removeFromEnd;
      }

      removeFromEnd = ( removeCount - removeFromStart );
    }

    private static int GetFetchDirection( long moveSize, int fetchSize )
    {
      return ( fetchSize != 0 )
               ? DataUtils.GetUnit( fetchSize )
               : DataUtils.GetUnit( moveSize );
    }

    private static bool IsValuableFetch( int fetchSize )
    {
      return Math.Abs( fetchSize ) > 1;
    }

    private static double RoundTowardZero( double value )
    {
      if( value < 0d )
        return Math.Ceiling( value );

      return Math.Floor( value );
    }

    private int GetPassiveFetchSize( JumpMoveAndFetchParameters parameters )
    {
      BufferInfo bufferInfo = this.GetBufferInfo( parameters.ExpectedFetchCount );
      BufferConfiguration configuration = bufferInfo.BufferConfiguration;

      // Set the new buffer capacity.
      int newCapacity = configuration.FindBufferCapacity( bufferInfo );
      this.SetBufferSize( newCapacity );

      // Retrieve the number of items to query in extra.
      bufferInfo = this.GetBufferInfo();
      int passiveFetchSize = configuration.FindPassivePreFetchSize( bufferInfo );

      int fetchDirection = BufferingEnumerator<T>.GetFetchDirection(
                             parameters.ExpectedMoveCount,
                             parameters.ExpectedFetchCount );

      // Calculate the fetch size to query for.
      int fetchSize = ( Math.Abs( parameters.ExpectedFetchCount ) + passiveFetchSize ) * fetchDirection;
      if( fetchSize == 0 )
      {
        fetchSize = ( parameters.ExpectedFetchCount != 0 )
                      ? parameters.ExpectedFetchCount
                      : Math.Sign( fetchDirection );
      }
      // Even if a passive fetch size has been given, make sure the extra items fetched will fit
      // in the buffer.
      else
      {
        int maximumFetchSize = newCapacity;

        // Take into account the center of gravity.
        if( bufferInfo.Size > 0 )
        {
          double centerOfGravity = bufferInfo.CenterOfGravity;
          double capacityRatio = ( fetchDirection >= 0 ) ? 1d - centerOfGravity : centerOfGravity;

          maximumFetchSize = ( int )Math.Floor( newCapacity * capacityRatio );
          maximumFetchSize = Math.Max( 0, Math.Min( newCapacity, maximumFetchSize ) );
        }

        // The buffer may drop some of the items.
        if( Math.Abs( fetchSize ) > maximumFetchSize )
        {
          fetchSize = maximumFetchSize * fetchDirection;
        }
      }

      if( Math.Abs( fetchSize ) < Math.Abs( parameters.ExpectedFetchCount ) )
      {
        fetchSize = parameters.ExpectedFetchCount;
      }

      return fetchSize;
    }

    private void GetActiveFetchSize( out int moveCount, out int fetchCount )
    {
      moveCount = 0;
      fetchCount = 0;

      BufferInfo bufferInfo = this.GetBufferInfo();
      BufferConfiguration configuration = bufferInfo.BufferConfiguration;

      // Set the new buffer capacity.
      int newCapacity = configuration.FindBufferCapacity( bufferInfo );
      this.SetBufferSize( newCapacity );

      // Find out the fetch size that is required to adjust the buffer.
      int sourcePositionIndex;
      int fetchSize = this.GetActivePreFetchSizeFromCenterOfGravity( out sourcePositionIndex );

      // There is nothing meaningful to fetch.
      if( !BufferingEnumerator<T>.IsValuableFetch( fetchSize ) )
        return;

      // Retrieve the size allowed for prefetching by the configuration.
      int activePreFetchSize = configuration.FindActivePreFetchSize( bufferInfo );

      // The current fetchSize may include some of the items in the buffer.
      // We must find out if the number of items that aren't in the buffer
      // is greater than the allowed fetch size.
      int direction = Math.Sign( fetchSize );
      int itemsInBuffer = ( direction >= 0 )
                            ? ( this.CachedItemsCount - sourcePositionIndex )
                            : sourcePositionIndex + 1;
      int maximumFetchSize = Math.Min( activePreFetchSize, Math.Abs( fetchSize ) - itemsInBuffer );

      // Make sure prefetching is still meaningful.
      if( !BufferingEnumerator<T>.IsValuableFetch( maximumFetchSize ) )
        return;

      moveCount = itemsInBuffer * direction;
      fetchCount = maximumFetchSize * direction;
    }

    private int GetActivePreFetchSizeFromCenterOfGravity( out int sourcePositionIndex )
    {
      sourcePositionIndex = -1;

      int maximumCacheSize = this.CacheSize;
      int cacheSize = this.CachedItemsCount;

      // Make sure prefetching is still meaningful.
      if( ( m_centerOfGravity == null )
        || ( maximumCacheSize < cacheSize )
        || ( maximumCacheSize < 3 )
        || ( ( this.IsCacheAtStart ) && ( this.IsCacheAtEnd ) ) )
        return 0;

      // Make sure the center of gravity is within the buffer.
      sourcePositionIndex = this.FindSourcePositionIndex( m_centerOfGravity, 0, 1 ).GetValueOrDefault( -1 );
      if( ( sourcePositionIndex < 0 ) || ( sourcePositionIndex >= cacheSize ) )
        return 0;

      BufferInfo bufferInfo = this.GetBufferInfo();
      double centerOfGravity = bufferInfo.CenterOfGravity;
      int centerOfGravityIndex = ( int )Math.Floor( centerOfGravity * ( maximumCacheSize - 1 ) );
      int centerOfGravityToStart = -centerOfGravityIndex - 1;
      int centerOfGravityToEnd = maximumCacheSize - centerOfGravityIndex;
      int fetchSize;

      // The buffer is allowed to grow further.
      if( cacheSize < maximumCacheSize )
      {
        int freeSpaceFromStart = centerOfGravityIndex - sourcePositionIndex;
        int freeSpaceToEnd = maximumCacheSize - ( centerOfGravityIndex + ( cacheSize - sourcePositionIndex ) );

        fetchSize = ( freeSpaceFromStart > freeSpaceToEnd )
                      ? centerOfGravityToStart
                      : centerOfGravityToEnd;
      }
      // Since the buffer is full, we will calculate the fetch size that is required
      // to place the target item in the center of gravity position once the buffer
      // is trimmed.
      else
      {
        double relativePosition = sourcePositionIndex / ( double )( maximumCacheSize - 1 );
        double relativeOffset = relativePosition - centerOfGravity;
        double centerOfGravityThreshold = bufferInfo.CenterOfGravityThreshold;

        // Active prefetching isn't required if the target item is near the
        // center of gravity's location.
        if( ( relativeOffset == 0d ) || ( Math.Abs( relativeOffset ) < centerOfGravityThreshold ) )
          return 0;

        int offset = ( int )BufferingEnumerator<T>.RoundTowardZero( relativeOffset * maximumCacheSize );
        if( offset == 0 )
          return 0;

        fetchSize = ( relativeOffset < 0d ) ? centerOfGravityToStart : centerOfGravityToEnd;
        fetchSize += offset;
      }

      // The center of gravity doesn't need to be respected when the targeted item is between
      // the center of gravity and the start of the source.
      if( this.IsCacheAtStart )
      {
        fetchSize = Math.Max( fetchSize, maximumCacheSize - sourcePositionIndex );
      }
      // The center of gravity doesn't need to be respected when the targeted item is between
      // the center of gravity and the end of the source.
      else if( this.IsCacheAtEnd )
      {
        fetchSize = Math.Min( fetchSize, cacheSize - maximumCacheSize - sourcePositionIndex - 1 );
      }

      return fetchSize;
    }

    private IAsyncResult BeginPassivePreFetching(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback callback,
      object state )
    {
      int fetchSize = this.GetPassiveFetchSize( parameters );
      JumpMoveAndFetchParameters preFetchParameters = parameters.CreateWithNewFetchCount( fetchSize );

      JumpMoveAndFetchAsyncResult asyncResult = new JumpMoveAndFetchAsyncResult(
                                                  BufferingEnumerator<T>.PassivePreFetchingCallId,
                                                  callback,
                                                  state,
                                                  parameters );

      Watch timer = new Watch();

      // Query the underlying enumerator with a boosted fetch size.
      asyncResult.AddDependentCall(
        ( cb, st ) =>
        {
          // Start the timer that will record the response time of the query.
          timer.Start();

          return base.BeginJumpMoveAndFetch( preFetchParameters, cb, st );
        },
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> childResult = base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar );

          // Keep some statistics about the query for configuration purpose.
          TimeSpan responseTime = timer.Stop();
          this.RecordRequest(
            new PassivePreFetchingBufferRequestInfo(
              childResult.ExpectedFetchCount,
              parameters.ExpectedFetchCount,
              responseTime,
              DateTime.Now ) );

          RelativeOffset endPositionOffset = childResult.EndPositionOffset;
          SourcePosition endPosition = childResult.EndPositionObject;
          bool result = childResult.Result;
          ICollection<T> fetchedItems = childResult.FetchedItems;

          // Remove the items that were fetched in extra in order to return only 
          // the requested items.
          if( ( childResult.FetchedItems != null ) && ( childResult.FetchedItems.Count > 0 ) )
          {
            if( Math.Abs( asyncResult.ExpectedFetchCount ) <= childResult.FetchedItems.Count )
            {
              if( asyncResult.ExpectedFetchCount == 0 )
              {
                fetchedItems = new List<T>();

                if( childResult.FetchedItems.Count > 0 )
                {
                  endPosition = new ItemPosition( childResult.FetchedItems.First() );
                  endPositionOffset = DataUtils.CalculateRelativeOffset( endPositionOffset, -childResult.GetFetchDisplacement() );
                }
              }
              else
              {
                List<T> itemList = childResult.FetchedItems.Take( Math.Abs( asyncResult.ExpectedFetchCount ) ).ToList();
                int expectedFetchDisplacement = asyncResult.ExpectedFetchCount - asyncResult.GetFetchUnit();

                endPosition = new ItemPosition( itemList[ itemList.Count - 1 ] );
                endPositionOffset = DataUtils.CalculateRelativeOffset( endPositionOffset, -( childResult.GetFetchDisplacement() - expectedFetchDisplacement ) );
                fetchedItems = itemList;
              }

              result = true;
            }
          }

          // Update the center of gravity.
          this.UpdateCenterOfGravity( endPosition as ItemPosition, fetchedItems );

          return new DependentCallResult(
                   new JumpMoveAndFetchResult<T>(
                     asyncResult,
                     childResult.ActualMoveCount,
                     fetchedItems,
                     result,
                     endPosition,
                     endPositionOffset,
                     childResult.TotalCount ) );
        } );

      asyncResult.Start();

      return asyncResult;
    }

    private JumpMoveAndFetchResult<T> EndPassivePreFetching( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( BufferingEnumerator<T>.PassivePreFetchingCallId );

      return asyncResult.GetCallResult<JumpMoveAndFetchResult<T>>();
    }

    private bool PeekBuffer(
      JumpMoveAndFetchParameters parameters,
      JumpMoveAndFetchAsyncResult asyncResult )
    {
      long actualMove;
      IList<T> items;
      SourcePosition endPosition;
      Nullable<int> sourcePositionIndex;
      bool operationCompleted;
      RelativeOffset endPositionOffset;
      EstimateInt64 totalCount;

      Watch timer = new Watch();
      timer.Start();

      bool result = this.CacheJumpMoveAndFetch(
                      parameters,
                      out actualMove,
                      out items,
                      out endPosition,
                      out sourcePositionIndex,
                      out operationCompleted,
                      out endPositionOffset,
                      out totalCount );

      TimeSpan responseTime = timer.Stop();

      // The buffer doesn't contain all the requested data.
      if( !operationCompleted )
        return false;

      bool isFetchingForward = ( BufferingEnumerator<T>.GetFetchDirection( parameters.ExpectedMoveCount, parameters.ExpectedFetchCount ) >= 0 );
      int inlineCount = this.GetItemsCountFromCenterOfGravity( isFetchingForward );

      this.RecordRequest(
        new SuccessBufferRequestInfo(
          parameters.ExpectedFetchCount,
          inlineCount,
          responseTime,
          DateTime.Now ) );

      BufferInfo bufferInfo = this.GetBufferInfo();
      BufferConfiguration configuration = bufferInfo.BufferConfiguration;

      // Set the new buffer capacity.
      int newCapacity = configuration.FindBufferCapacity( bufferInfo );
      this.SetBufferSize( newCapacity );

      // Update the center of gravity.
      this.UpdateCenterOfGravity( endPosition as ItemPosition, items );

      // Start prefetching actively in order to move the center of gravity.
      this.StartPreFetching();

      // Return the data that was already in the buffer.
      JumpMoveAndFetchResult<T> queryResult = new JumpMoveAndFetchResult<T>(
                                                    asyncResult,
                                                    actualMove,
                                                    items,
                                                    result,
                                                    endPosition,
                                                    endPositionOffset,
                                                    totalCount );

      asyncResult.StartSync( queryResult );

      return true;
    }

    private void EnqueueQuery(
      JumpMoveAndFetchParameters parameters,
      JumpMoveAndFetchAsyncResult asyncResult )
    {
      this.StopPreFetching();

      bool isQueryRunnable = !this.IsAnyQueryRunning();

      m_requestsQueue.AddLast( asyncResult );

      // The query may be launched right now only if no other query is running.
      if( isQueryRunnable )
      {
        this.DequeueQuery( false );
      }
    }

    private void DequeueQuery( bool isAsyncResult )
    {
      if( ( m_requestsQueue.Count <= 0 ) || ( this.IsActivePreFetchingQueryRunning() ) )
        return;

      JumpMoveAndFetchAsyncResult asyncResult = m_requestsQueue.First.Value;
      JumpMoveAndFetchParameters parameters = asyncResult.GetParameters();

      // Some queries have modified the buffer since last time.  Check out the buffer
      // first in case the requested data is in there.
      if( isAsyncResult )
      {
        JumpMoveAndFetchAsyncResult cachedAsyncResult = new JumpMoveAndFetchAsyncResult( asyncResult.CallId, null, null, parameters );

        // The requested data is in the buffer.
        if( this.PeekBuffer( parameters, cachedAsyncResult ) )
        {
          Debug.Assert( cachedAsyncResult.CompletedSynchronously );

          JumpMoveAndFetchResult<T> cachedResult;

          try
          {
            cachedResult = cachedAsyncResult.GetCallResult<JumpMoveAndFetchResult<T>>();
          }
          finally
          {
            m_requestsQueue.Remove( asyncResult );
          }

          // Schedule the next query.
          this.StartNextQuery();

          asyncResult.StartAsync( cachedResult );

          return;
        }
      }

      // Start the query that will get the requested items from the underlying enumerator.
      JumpMoveAndFetchAsyncResult passiveAsyncResult = new JumpMoveAndFetchAsyncResult( asyncResult.CallId, null, null, parameters );
      passiveAsyncResult.Start(
        ( cb, st ) => this.BeginPassivePreFetching( parameters, cb, st ),
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> result;

          try
          {
            result = this.EndPassivePreFetching( iar );
          }
          finally
          {
            m_requestsQueue.Remove( asyncResult );
          }

          // Schedule the next query.
          this.StartNextQuery();

          if( ( iar.CompletedSynchronously ) && ( !isAsyncResult ) )
          {
            asyncResult.StartSync( result );
          }
          else
          {
            asyncResult.StartAsync( result );
          }

          return new DependentCallResult( null );
        } );
    }

    private void PreFetch()
    {
      // A query is actually running.
      if( this.IsAnyQueryRunning() )
        return;

      int moveSize;
      int fetchSize;
      this.GetActiveFetchSize( out moveSize, out fetchSize );

      // Make sure the fetch size is meaningful.
      if( fetchSize == 0 )
        return;

      JumpMoveAndFetchParameters parameters = new JumpMoveAndFetchParameters(
                                                m_centerOfGravity,
                                                moveSize,
                                                fetchSize );

      JumpMoveAndFetchAsyncResult asyncResult = new JumpMoveAndFetchAsyncResult(
                                                  BufferingEnumerator<T>.ActivePreFetchingCallId,
                                                  this.PreFetchCallback,
                                                  null,
                                                  parameters );

      Watch timer = new Watch();

      asyncResult.Start(
        ( cb, st ) =>
        {
          // Start the timer that will record the response time of the query.
          timer.Start();

          return base.BeginJumpMoveAndFetch( parameters, cb, st );
        },
        ( par, iar ) =>
        {
          JumpMoveAndFetchResult<T> result = base.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )iar );

          // Keep some statistics about the query for configuration purpose.
          TimeSpan responseTime = timer.Stop();
          int fetchCount = ( result.FetchedItems != null ) ? result.FetchedItems.Count : 0;

          this.RecordRequest(
            new ActivePreFetchingBufferRequestInfo(
              fetchCount,
              responseTime,
              DateTime.Now ) );

          return new DependentCallResult( result );
        } );

      if( asyncResult.CompletedSynchronously )
      {
        this.StartNextQuery();
      }
      else
      {
        m_preFetchRequest = asyncResult;
      }
    }

    private void PreFetchCallback( IAsyncResult asyncResult )
    {
      if( asyncResult.CompletedSynchronously )
        return;

      if( asyncResult == m_preFetchRequest )
      {
        m_preFetchRequest = null;

        this.StartNextQuery();
      }
    }

    private void StartNextQuery()
    {
      if( m_requestsQueue.Count == 0 )
      {
        this.StartPreFetching();
      }
      else
      {
        this.StartFetching();
      }
    }

    private bool IsAnyQueryRunning()
    {
      return ( this.IsActivePreFetchingQueryRunning() )
          || ( m_requestsQueue.Count > 0 );
    }

    private bool IsActivePreFetchingQueryRunning()
    {
      return ( m_preFetchRequest != null );
    }

    private void SetBufferSize( int capacity )
    {
      this.SetCacheSize( capacity, 0 );
    }

    private BufferInfo GetBufferInfo()
    {
      return this.GetBufferInfo( this.CacheSize );
    }

    private BufferInfo GetBufferInfo( int fetchSize )
    {
      if( m_bufferInfo != null )
      {
        int cacheCapacity = Math.Max( this.CacheSize, Math.Abs( fetchSize ) );
        int cacheSize = this.CachedItemsCount;

        m_bufferInfo.Update( cacheSize, cacheCapacity, m_requestsHistory );

        // Make sure the buffer info has been initialized by the same BufferConfiguration.
        BufferConfiguration configuration = this.GetBufferConfiguration();
        if( configuration != null )
        {
          BufferConfiguration.Prepare( configuration, m_bufferInfo );
        }
      }

      return m_bufferInfo;
    }

    private BufferConfiguration GetBufferConfiguration()
    {
      BufferConfiguration configuration = null;
      if( m_bufferManager != null )
      {
        configuration = m_bufferManager.BufferConfiguration;
      }

      if( configuration == null )
      {
        if( m_bufferConfiguration == null )
        {
          m_bufferConfiguration = new DisabledBufferConfiguration();
        }

        configuration = m_bufferConfiguration;
      }

      return configuration;
    }

    private int GetItemsCountFromCenterOfGravity( bool isFetchingForward )
    {
      // Make sure the center of gravity is within the buffer.
      if( m_centerOfGravity != null )
      {
        int cacheSize = this.CachedItemsCount;
        int centerOfGravityIndex = this.FindSourcePositionIndex( m_centerOfGravity, 0, 1 ).GetValueOrDefault( -1 );

        if( ( centerOfGravityIndex >= 0 ) && ( centerOfGravityIndex < cacheSize ) )
          return ( isFetchingForward )
                   ? cacheSize - centerOfGravityIndex
                   : centerOfGravityIndex + 1;
      }

      return 0;
    }

    private void UpdateCenterOfGravity( ItemPosition position, ICollection<T> items )
    {
      if( position != null )
      {
        m_centerOfGravity = position;
      }
      else if( ( items != null ) && ( items.Count > 0 ) )
      {
        m_centerOfGravity = new ItemPosition( items.Last() );
      }
    }

    #region IDisposable Members

    protected override void Dispose( bool disposing )
    {
      if( m_bufferInfo != null )
      {
        m_bufferInfo.CleanUp();
      }

      m_bufferInfo = null;
      m_bufferConfiguration = null;
      m_bufferManager = null;
      m_centerOfGravity = null;
      m_requestsQueue.Clear();
      m_requestsHistory.Clear();

      m_preFetchRequest = null;
      m_preFetchDispatcherOperation = null;
      m_fetchDispatcherOperation = null;

      base.Dispose( disposing );
    }

    #endregion

    #region Query Scheduling Methods

    private void StartFetching()
    {
      // There is no query to run, a prefetching query is already running
      // or a query has already been scheduled.
      if( ( m_requestsQueue.Count <= 0 )
        || ( this.IsActivePreFetchingQueryRunning() )
        || ( m_fetchDispatcherOperation != null ) )
        return;

      // Schedule the fetching query.
      DispatcherOperation dop = null;
      Action fetch =
        () =>
        {
          // Make sure the query hasn't been canceled.
          if( dop == m_fetchDispatcherOperation )
          {
            m_fetchDispatcherOperation = null;

            this.DequeueQuery( true );
          }
        };

      dop = UIDispatcher.Instance.BeginInvoke( fetch );
      m_fetchDispatcherOperation = dop;
    }

    private void StartPreFetching()
    {
      // Active prefetching has been disabled.
      if( this.CacheSize == 0 )
      {
        m_preFetchDispatcherOperation = null;

        return;
      }

      // A prefetching query is already running or the center of gravity isn't appropriate.
      if( ( this.IsActivePreFetchingQueryRunning() )
        || ( m_centerOfGravity == null )
        || ( m_preFetchDispatcherOperation != null ) )
        return;

      // Schedule the prefetching query.
      DispatcherOperation dop = null;
      Action preFetch =
        () =>
        {
          // Make sure the query hasn't been canceled.
          if( dop == m_preFetchDispatcherOperation )
          {
            m_preFetchDispatcherOperation = null;

            this.PreFetch();
          }
        };

      dop = UIDispatcher.Instance.BeginInvoke( preFetch );
      m_preFetchDispatcherOperation = dop;
    }

    private void StopPreFetching()
    {
      m_preFetchDispatcherOperation = null;
    }

    private JumpMoveAndFetchAsyncResult m_preFetchRequest; //null
    private DispatcherOperation m_preFetchDispatcherOperation; //null
    private DispatcherOperation m_fetchDispatcherOperation; //null

    #endregion

    #region Request Statistics Methods

    private void RecordRequest( BufferRequestInfo request )
    {
      if( ( request == null ) || ( m_requestsHistory == null ) )
        return;

      BufferInfo bufferInfo = this.GetBufferInfo();
      if( bufferInfo == null )
        return;

      int samplesCount = bufferInfo.RequestsHistoryLength;
      while( ( m_requestsHistory.Count >= samplesCount )
          && ( m_requestsHistory.Count > 0 ) )
      {
        m_requestsHistory.RemoveLast();
      }

      m_requestsHistory.AddFirst( request );
    }

    private LinkedList<BufferRequestInfo> m_requestsHistory = new LinkedList<BufferRequestInfo>();

    #endregion

    #region Private Fields

    private BufferConfiguration m_bufferConfiguration; //null
    private IBufferConfigurable m_bufferManager; //null
    private BufferInfo m_bufferInfo = new BufferInfo();
    private ItemPosition m_centerOfGravity; //null
    private LinkedList<JumpMoveAndFetchAsyncResult> m_requestsQueue = new LinkedList<JumpMoveAndFetchAsyncResult>();

    #endregion

    #region Private Watch Nested Type

    private class Watch
    {
      internal void Start()
      {
        if( m_running )
          throw new InvalidOperationException();

        m_running = true;
        m_startValue = Environment.TickCount;
      }

      internal TimeSpan Stop()
      {
        if( !m_running )
          throw new InvalidOperationException();

        int endValue = Environment.TickCount;
        m_running = false;

        long interval;

        if( endValue >= m_startValue )
        {
          interval = ( endValue - m_startValue );
        }
        else
        {
          interval = ( int.MaxValue - m_startValue ) + ( endValue - int.MinValue );
        }

        return TimeSpan.FromMilliseconds( interval );
      }

      private bool m_running; //false
      private int m_startValue; //0
    }

    #endregion
  }
}
